#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * https://leetcode.cn/problems/surrounded-regions/description/
 * 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。
 如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 *
 *
 * */

/*
 * todo 思路是参考的 第一步把 地图周边的相邻的O全部标记为A
 * 然后遍历把 非X非O的全部标记为X
 * 最后把A全部改为 O
 *
 * */
int dir[4][2] = {
        {1,  0},//上
        {-1, 0},//下
        {0,  1},//左边
        {0,  -1},//右边
};

//本dfs 就是从边界的一开始进行循环
void dfs(vector<vector<char>> &board, int row, int col) {

    board[row][col] = 'A';
    // 分别向上下左右进行
    for (int i = 0; i < 4; ++i) {
        int n_row = row + dir[i][0];
        int n_col = col + dir[i][1];
        //如果不符合
        if (n_row < 0 || n_col < 0 || n_row >= board.size() || n_col >= board[0].size())
            continue;
        if (board[n_row][n_col] == 'A' || board[n_row][n_col] == 'X')
            continue;
        dfs(board, n_row, n_col);
    }

}


void solve(vector<vector<char>> &board) {

    //上面 和下面
    for (int i = 0; i < board[0].size(); ++i) {
        if (board[0][i] == 'O')
            dfs(board, 0, i);

        if (board[board.size() - 1][i] == 'O')
            dfs(board, board.size() - 1, i);

    }

    // 左边和右边
    for (int i = 0; i < board.size(); ++i) {

        if (board[i][0] == 'O')
            dfs(board, i, 0);
        if (board[i][board[0].size() - 1] == 'O')
            dfs(board, i, board[0].size() - 1);
    }

    //恢复结果
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[0].size(); ++j) {
            if (board[i][j] == 'O')
                board[i][j] = 'X';
            if (board[i][j] == 'A')
                board[i][j] = 'O';

        }

    }


}